3
3.0

Jun 25, 2018
06/18

by
Md. Jawaherul Alam; William Evans; Stephen G. Kobourov; Sergey Pupyrev; Jackson Toeniskoetter; Torsten Ueckerdt

texts

######
eye 3

######
favorite 0

######
comment 0

We study contact representations of graphs in which vertices are represented by axis-aligned polyhedra in 3D and edges are realized by non-zero area common boundaries between corresponding polyhedra. We show that for every 3-connected planar graph, there exists a simultaneous representation of the graph and its dual with 3D boxes. We give a linear-time algorithm for constructing such a representation. This result extends the existing primal-dual contact representations of planar graphs in 2D...

Topics: Computational Geometry, Computing Research Repository, Discrete Mathematics, Computing Research...

Source: http://arxiv.org/abs/1501.00304

0
0.0

Jun 25, 2018
06/18

by
Md. Jawaherul Alam; David Eppstein; Michael Kaufmann; Stephen G. Kobourov; Sergey Pupyrev; Andre Schulz; Torsten Ueckerdt

texts

######
eye 0

######
favorite 0

######
comment 0

We study representations of graphs by contacts of circular arcs, CCA-representations for short, where the vertices are interior-disjoint circular arcs in the plane and each edge is realized by an endpoint of one arc touching the interior of another. A graph is (2,k)-sparse if every s-vertex subgraph has at most 2s - k edges, and (2, k)-tight if in addition it has exactly 2n - k edges, where n is the number of vertices. Every graph with a CCA- representation is planar and (2, 0)-sparse, and it...

Topics: Computational Geometry, Computing Research Repository, Discrete Mathematics, Computing Research...

Source: http://arxiv.org/abs/1501.00318

0
0.0

Jun 30, 2018
06/18

by
Franck Delaplace

texts

######
eye 0

######
favorite 0

######
comment 0

Different Boolean networks may reveal similar dynamics although their definition differs, then preventing their distinction from the observations. This raises the question about the sufficiency of a particular Boolean network for properly reproducing a modeled phenomenon to make realistic predictions. The question actually depends on the invariant properties of behaviorally similar Boolean networks. In this article, we address this issue by considering that the similarity is formalized by...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1411.6135

0
0.0

Jun 29, 2018
06/18

by
Benjamin Girault; Paulo Gonçalves; Shrikanth Narayanan; Antonio Ortega

texts

######
eye 0

######
favorite 0

######
comment 0

The graph translation operator has been defined with good spectral properties in mind, and in particular with the end goal of being an isometric operator. Unfortunately, the resulting definitions do not provide good intuitions on a vertex-domain interpretation. In this paper, we show that this operator does have a vertex-domain interpretation as a diffusion operator using a polynomial approximation. We show that its impulse response exhibit an exponential decay of the energy way from the...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1609.08820

0
0.0

Jun 30, 2018
06/18

by
Konrad Kułakowski

texts

######
eye 0

######
favorite 0

######
comment 0

Comparing alternatives in pairs is a well-known method of ranking creation. Experts are asked to perform a series of binary comparisons and then, using mathematical methods, the final ranking is prepared. As experts conduct the individual assessments, they may not always be consistent. The level of inconsistency among individual assessments is widely accepted as a measure of the ranking quality. The higher the ranking quality, the greater its credibility. One way to determine the level of...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1702.01126

0
0.0

Jun 29, 2018
06/18

by
Zakir Deniz; Tınaz Ekim

texts

######
eye 0

######
favorite 0

######
comment 0

A graph $G$ is \emph{equimatchable} if every maximal matching of $G$ has the same cardinality. We are interested in equimatchable graphs such that the removal of any edge from the graph preserves the equimatchability. We call an equimatchable graph $G$ \emph{edge-stable} if $G\setminus {e}$ is equimatchable for any $e \in E(G)$. After noticing that edge-stable equimatchable graphs are either 2-connected factor-critical or bipartite, we characterize edge-stable equimatchable graphs. This...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1602.09127

0
0.0

Jun 29, 2018
06/18

by
Robert Bredereck; Vincent Froese; Marcel Koseler; Marcelo Garlet Millani; André Nichterlein; Rolf Niedermeier

texts

######
eye 0

######
favorite 0

######
comment 0

There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed graphs; herein, we focus on arc insertions. To this end, our general two-stage framework consists of efficiently solving a problem-specific number problem transferring its solution to a solution for the graph problem by applying flow computations. In...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1604.06302

5
5.0

Jun 28, 2018
06/18

by
Jarkko Peltomäki; Markus Whiteland

texts

######
eye 5

######
favorite 0

######
comment 0

We introduce a square root map on Sturmian words and study its properties. Given a Sturmian word of slope $\alpha$, there exists exactly six minimal squares in its language (a minimal square does not have a square as a proper prefix). A Sturmian word $s$ of slope $\alpha$ can be written as a product of these six minimal squares: $s = X_1^2 X_2^2 X_3^2 \cdots$. The square root of $s$ is defined to be the word $\sqrt{s} = X_1 X_2 X_3 \cdots$. The main result of this paper is that that $\sqrt{s}$...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1509.06349

3
3.0

Jun 26, 2018
06/18

by
W. W. Koczkodaj; J. Szybowski; E. Wajch

texts

######
eye 3

######
favorite 0

######
comment 0

This study presents an abelian group approach to analyzing inconsistency in pairwise comparisons. A notion of an inconsistency indicator map on a group, taking values in an abelian linearly ordered group, is introduced. For it, metrics and generalized metrics are utilized. Every inconsistency indicator map generates both a metric on a group and an inconsistency indicator of an arbitrary pairwise comparisons matrix over the group.

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1502.06160

0
0.0

Jun 29, 2018
06/18

by
Argyrios Deligkas; George B. Mertzios; Paul G. Spirakis

texts

######
eye 0

######
favorite 0

######
comment 0

Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GreedyMatching. In wide contrast to the maximum weight matching problem, for which many efficient algorithms are known, we prove that GreedyMatching is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1602.05909

0
0.0

Jun 29, 2018
06/18

by
Samiksha Sarwari; Shrisha Rao

texts

######
eye 0

######
favorite 0

######
comment 0

We define a \emph{thermal network}, which is a network where the flow functionality of a node depends upon its temperature. This model is inspired by several types of real-life networks, and generalizes some conventional network models wherein nodes have fixed capacities and the problem is to maximize the flow through the network. In a thermal network, the temperature of a node increases as traffic moves through it, and nodes may also cool spontaneously over time, or by employing cooling...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1607.02637

0
0.0

Jun 29, 2018
06/18

by
Hosam Abdo; Darko Dimitrov; Wei Gao

texts

######
eye 0

######
favorite 0

######
comment 0

Measures of the irregularity of chemical graphs could be helpful for QSAR/QSPR studies and for the descriptive purposes of biological and chemical properties, such as melting and boiling points, toxicity and resistance. Here we consider the following four established irregularity measures: the irregularity index by Albertson, the total irregularity, the variance of vertex degrees and the Collatz-Sinogowitz index. Through the means of graph structural analysis and derivation, we study the...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1608.05235

0
0.0

Jun 28, 2018
06/18

by
Aurore Alcolei; Kévin Perrot; Sylvain Sené

texts

######
eye 0

######
favorite 0

######
comment 0

Boolean automata networks (BANs) are a well established model for biological regulation systems such as neural networks or genetic networks. Studies on the dynamics of BANs, whether it is synchronous or asynchronous, have mainly focused on monotonic networks, where fundamental questions on the links relating their static and dynamical properties have been raised and addressed. This paper explores analogous questions on asynchronous non-monotonic networks, xor-BANs, that are BANs where all the...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1510.05452

0
0.0

Jun 28, 2018
06/18

by
Jingyuan Chen; Yun Li; Lijun Ji

texts

######
eye 0

######
favorite 0

######
comment 0

Optical orthogonal signature pattern codes (OOSPCs) play an important role in a novel type of optical code-division multiple-access (CDMA) network for 2-dimensional image transmission. There is a one-to-one correspondence between an $(m, n, w, \lambda)$-OOSPC and a $(\lambda+1)$-$(mn,w,1)$ packing design admitting an automorphism group isomorphic to $\mathbb{Z}_m\times \mathbb{Z}_n$. In 2010, Sawa gave the first infinite class of $(m, n, 4, 2)$-OOSPCs by using $S$-cyclic Steiner quadruple...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1511.09289

1
1.0

Jun 28, 2018
06/18

by
Laurent Bulteau; Vincent Froese; Sepp Hartung; Rolf Niedermeier

texts

######
eye 1

######
favorite 0

######
comment 0

Co-clustering, that is, partitioning a numerical matrix into homogeneous submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard as well as a number of relevant polynomial-time solvable special cases, thus...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1512.05693

0
0.0

Jun 29, 2018
06/18

by
Pietro Cenciarelli; Daniele Gorla; Ivano Salvo

texts

######
eye 0

######
favorite 0

######
comment 0

We consider network models where information items flow %are sent from a source to a sink node. We start with a model where routing is constrained by energy available on nodes in finite supply (like in Smartdust) and efficiency is related to energy consumption. We characterize graph topologies ensuring that every saturating flow under every energy-to-node assignment is maximum and provide a polynomial-time algorithm for checking this property. We then consider the standard flow networks with...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1603.01983

0
0.0

Jun 29, 2018
06/18

by
Maurice Margenstern

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper, we construct a weakly universal cellular automaton in the heptagrid, the tessellation $\{7,3\}$ which is not rotation invariant but which is truly planar. This result, under these conditions, cannot be improved for the tessellations $\{p,3\}$.

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1606.09488

0
0.0

Jun 29, 2018
06/18

by
Karthekeyan Chandrasekaran; Corinna Gottschalk; Jochen Könemann; Britta Peis; Daniel Schmand; Andreas Wierz

texts

######
eye 0

######
favorite 0

######
comment 0

Stabilization of graphs has received substantial attention in recent years due to its connection to game theory. Stable graphs are exactly the graphs inducing a matching game with non-empty core. They are also the graphs that induce a network bargaining game with a balanced solution. A graph with weighted edges is called stable if the maximum weight of an integral matching equals the cost of a minimum fractional weighted vertex cover. If a graph is not stable, it can be stabilized in different...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1608.06797

0
0.0

Jun 29, 2018
06/18

by
Petr Gregor; Riste Skrekovski; Vida Vukasinovic

texts

######
eye 0

######
favorite 0

######
comment 0

Simultaneous broadcasting of multiple messages from the same source vertex in synchronous networks is considered under restrictions that each vertex receives at most one message in a unit time step, every received message can be sent out only in the next time step, no message is sent to already informed vertex. The number of outgoing messages in unrestricted, messages have unit length, and we assume full-duplex mode. In [9] we developed a concept of level-disjoint partitions to study...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1609.01116

1
1.0

Jun 29, 2018
06/18

by
Indranil Banerjee; Dana Richards

texts

######
eye 1

######
favorite 0

######
comment 0

In this short note we give the routing number of pyramid graph under the \textit{routing via matching} model introduced by Alon et al\cite{5}. This model can be viewed as a communication scheme on a distributed network. The nodes in the network can communicate via matchings (a step), where a node exchanges data with its partner. Formally, given a connected graph $G$ with vertices labeled from $[1,...,n]$ and a permutation $\pi$ giving the destination of pebbles on the vertices the problem is to...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1611.07933

0
0.0

Jun 30, 2018
06/18

by
Xiaofang Jiang; Qinghui Liu; Natarajan Parthiban; R. Sundara Rajan

texts

######
eye 0

######
favorite 0

######
comment 0

A linear arrangement is a labeling or a numbering or a linear ordering of the vertices of a graph. In this paper we solve the minimum linear arrangement problem for bijective connection graphs (for short BC graphs) which include hypercubes, M\"{o}bius cubes, crossed cubes, twisted cubes, locally twisted cube, spined cube, $Z$-cubes, etc. as the subfamilies.

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1703.01149

0
0.0

Jun 29, 2018
06/18

by
Mong-Jen Kao; Hai-Lun Tu; D. T. Lee

texts

######
eye 0

######
favorite 0

######
comment 0

We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph $G=(V,E)$ with a maximum edge size $f$. Each edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset such that the demands of the edges can be covered by the capacities of the vertices and the multiplicity of each vertex does not...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1609.02640

0
0.0

Jun 29, 2018
06/18

by
Raka Jovanovic; Islam Safak Bayram; Stefan Voss

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper, we present a constructive heuristic algorithm for the $2$-connected $m$-dominating set problem. It is based on a greedy heuristic in which a 2-connected subgraph is iteratively extended with suitable open ears. The growth procedure is an adaptation of the breadth-first-search which efficiently manages to find open ears. Further, a heuristic function is defined for selecting the best ear out of a list of candidates. The performance of the basic approach is improved by adding a...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1609.05662

0
0.0

Jun 28, 2018
06/18

by
K. Krishna Mohan Reddy; P. Renjith; N. Sadagopan

texts

######
eye 0

######
favorite 0

######
comment 0

For a connected labelled graph $G$, a {\em spanning tree} $T$ is a connected and an acyclic subgraph that spans all vertices of $G$. In this paper, we consider a classical combinatorial problem which is to list all spanning trees of $G$. A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1511.01696

0
0.0

Jun 30, 2018
06/18

by
Ngoc Khang Le

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper, we propose a polynomial-time algorithm to test whether a given graph contains a subdivision of $K_4$ as an induced subgraph.

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1703.04637

0
0.0

Jun 26, 2018
06/18

by
Marc Hellmuth; Nicolas Wieseke

texts

######
eye 0

######
favorite 0

######
comment 0

Symbolic ultrametrics define edge-colored complete graphs K_n and yield a simple tree representation of K_n. We discuss, under which conditions this idea can be generalized to find a symbolic ultrametric that, in addition, distinguishes between edges and non-edges of arbitrary graphs G=(V,E) and thus, yielding a simple tree representation of G. We prove that such a symbolic ultrametric can only be defined for G if and only if G is a so-called cograph. A cograph is uniquely determined by a...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1501.03931

3
3.0

Jun 28, 2018
06/18

by
Agnes Cseh; Telikepalli Kavitha

texts

######
eye 3

######
favorite 0

######
comment 0

Given a bipartite graph G = (A u B, E) with strict preference lists and and edge e*, we ask if there exists a popular matching in G that contains the edge e*. We call this the popular edge problem. A matching M is popular if there is no matching M' such that the vertices that prefer M' to M outnumber those that prefer M to M'. It is known that every stable matching is popular; however G may have no stable matching with the edge e* in it. In this paper we identify another natural subclass of...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1508.00614

0
0.0

Jun 30, 2018
06/18

by
Gunther Schmidt; Michael Winter

texts

######
eye 0

######
favorite 0

######
comment 0

This is in some sense an addendum to the book Relational Mathematics by the first-named author. It originated from work on diverse other topics during which a lot of purely relational results with broad applicability have been produced. These include results on domain construction with novel formulae for existential and inverse image, a relational calculus for binary mappings, and the development of a formally derived relational calculus of Kronecker-, strict fork-, and strict join-operators....

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1403.6957

1
1.0

Jun 30, 2018
06/18

by
Stavros G. Kolliopoulos; Yannis Moysoglou

texts

######
eye 1

######
favorite 0

######
comment 0

Exploring the power of linear programming for combinatorial optimization problems has been recently receiving renewed attention after a series of breakthrough impossibility results. From an algorithmic perspective, the related questions concern whether there are compact formulations even for problems that are known to admit polynomial-time algorithms. We propose a framework for proving lower bounds on the size of extended formulations. We do so by introducing a specific type of extended...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1410.1150

0
0.0

Jun 28, 2018
06/18

by
Pooja Pandey; Abraham P. Punnen

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper we identify some inaccuracies in the paper by R.R. Saxena and S.R. Arora, A Linearization technique for solving the Quadratic Set Covering Problem, Optimization, 39 (1997) 33-42. In particular, we observe that their algorithm need not guarantee optimality, contrary to what is claimed. Experimental analysis with the algorithm has been carried out to evaluate its merit as a heuristic and compared with CPLEX. The results disclose that for some class of problems the algorithm is...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1509.06305

0
0.0

Jun 26, 2018
06/18

by
Eleni C. Akrida; Leszek Gasieniec; George B. Mertzios; Paul G. Spirakis

texts

######
eye 0

######
favorite 0

######
comment 0

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of $n$ vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex $u$ to vertex $v$ is a path from $u$ to $v$ where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a $(u,v)$-journey for any pair of vertices $u,v,~u\not= v$. We first give a simple polynomial-time...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1502.04579

1
1.0

Jun 28, 2018
06/18

by
Sandip Das; Soumen Nandi; Sagnik Sen

texts

######
eye 1

######
favorite 0

######
comment 0

An $(m,n)$-colored mixed graph $G$ is a graph with its arcs having one of the $m$ different colors and edges having one of the $n$ different colors. A homomorphism $f$ of an $(m,n)$-colored mixed graph $G$ to an $(m,n)$-colored mixed graph $H$ is a vertex mapping such that if $uv$ is an arc (edge) of color $c$ in $G$, then $f(u)f(v)$ is an arc (edge) of color $c$ in $H$. The \textit{$(m,n)$-colored mixed chromatic number} $\chi_{(m,n)}(G)$ of an $(m,n)$-colored mixed graph $G$ is the order...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1508.07222

0
0.0

Jun 29, 2018
06/18

by
Abhijeet Khopkar

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper, we focus on a generalised version of Gabriel graphs known as Locally Gabriel graphs ($LGGs$) and Unit distance graphs ($UDGs$) on convexly independent point sets. $UDGs$ are sub graphs of $LGGs$. We give a simpler proof for the claim that $LGGs$ on convex independent point sets have $2n \log n + O(n)$ edges. Then we prove that unit distance graphs on convex independent point sets have $O(n)$ edges improving the previous known bound of $O(n \log n)$.

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1605.08066

1
1.0

Jun 29, 2018
06/18

by
Bernd Gärtner; Antonis Thomas

texts

######
eye 1

######
favorite 0

######
comment 0

Random Edge is the most natural randomized pivot rule for the simplex algorithm. Considerable progress has been made recently towards fully understanding its behavior. Back in 2001, Welzl introduced the concepts of \emph{reachmaps} and \emph{niceness} of Unique Sink Orientations (USO), in an effort to better understand the behavior of Random Edge. In this paper, we initiate the systematic study of these concepts. We settle the questions that were asked by Welzl about the niceness of (acyclic)...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1606.07709

0
0.0

Jun 28, 2018
06/18

by
Zoran Maksimovic

texts

######
eye 0

######
favorite 0

######
comment 0

This work introduces a multidimensional generalization of the maximum bisection problem. A mixed integer linear programming formulation is proposed with the proof of its correctness. The numerical tests, made on the randomly generated graphs, indicates that the multidimensional generalization is more difficult to solve than the original problem.

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1506.07731

0
0.0

Jun 30, 2018
06/18

by
Martiniano Eguía; Francisco J. Soulignac

texts

######
eye 0

######
favorite 0

######
comment 0

In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A diclique of a digraph is a pair $V \to W$ of sets of vertices such that $v \to w$ is an arc for every $v \in V$ and $w \in W$. An arc $v \to w$ is disimplicial when $N^-(w) \to N^+(v)$ is a diclique. We show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1403.1628

0
0.0

Jun 30, 2018
06/18

by
Konstantinos Georgiou; Evangelos Kranakis; Danny Krizanc

texts

######
eye 0

######
favorite 0

######
comment 0

Consider a theatre consisting of $m$ rows each containing $n$ seats. Theatregoers enter the theatre along aisles and pick a row which they enter along one of its two entrances so as to occupy a seat. Assume they select their seats uniformly and independently at random among the empty ones. A row of seats is narrow and an occupant who is already occupying a seat is blocking passage to new incoming theatregoers. As a consequence, occupying a specific seat depends on the courtesy of theatregoers...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1403.1988

1
1.0

Jun 30, 2018
06/18

by
Francisco J. Soulignac

texts

######
eye 1

######
favorite 0

######
comment 0

We consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version, a proper circular-arc (PCA) model $\cal M$ is given and the goal is to obtain an equivalent UCA model $\cal U$. We show a linear time algorithm with negative certification that can also be implemented to run in logspace. In the bounded version, $\cal M$ is given together with some lower and upper bounds that the beginning points of...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1408.3443

0
0.0

Jun 29, 2018
06/18

by
Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

texts

######
eye 0

######
favorite 0

######
comment 0

A substring Q of a string S is called a shortest unique substring (SUS) for interval [s,t] in S, if Q occurs exactly once in S, this occurrence of Q contains interval [s,t], and every substring of S which contains interval [s,t] and is shorter than Q occurs at least twice in S. The SUS problem is, given a string S, to preprocess S so that for any subsequent query interval [s,t] all the SUSs for interval [s,t] can be answered quickly. When s = t, we call the SUSs for [s,t] as point SUSs, and...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1609.07220

0
0.0

Jun 29, 2018
06/18

by
P. Renjith; N. Sadagopan

texts

######
eye 0

######
favorite 0

######
comment 0

In this paper, we investigate the well-studied Hamiltonian cycle problem, and present an interesting dichotomy result on split graphs. T. Akiyama, T. Nishizeki, and N. Saito \cite{akiyama} have shown that the Hamiltonian cycle problem is NP-complete in planar bipartite graph with maximum degree $3$. Using this reduction, we show that the Hamiltonian cycle problem is NP-complete in split graphs. In particular, we show that the problem is NP-complete in $K_{1,5}$-free split graphs. Further, we...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1610.00855

0
0.0

Jun 30, 2018
06/18

by
Marc Hellmuth; Adrian Fritz; Nicolas Wieseke; Peter F. Stadler

texts

######
eye 0

######
favorite 0

######
comment 0

The modular decomposition of a graph $G=(V,E)$ does not contain prime modules if and only if $G$ is a cograph, that is, if no quadruple of vertices induces a simple connected path $P_4$. The cograph editing problem consists in inserting into and deleting from $G$ a set $F$ of edges so that $H=(V,E\Delta F)$ is a cograph and $|F|$ is minimum. This NP-hard combinatorial optimization problem has recently found applications, e.g., in the context of phylogenetics. Efficient heuristics are hence of...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1702.07499

0
0.0

Jun 30, 2018
06/18

by
Jeffrey M. Dudek; Kuldeep S. Meel; Moshe Y. Vardi

texts

######
eye 0

######
favorite 0

######
comment 0

The runtime performance of modern SAT solvers on random $k$-CNF formulas is deeply connected with the 'phase-transition' phenomenon seen empirically in the satisfiability of random $k$-CNF formulas. Recent universal hashing-based approaches to sampling and counting crucially depend on the runtime performance of SAT solvers on formulas expressed as the conjunction of both $k$-CNF and XOR constraints (known as $k$-CNF-XOR formulas), but the behavior of random $k$-CNF-XOR formulas is unexplored in...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1702.08392

0
0.0

Jun 30, 2018
06/18

by
Glencora Borradaile; Jeff Erickson; Hung Le; Robbie Weber

texts

######
eye 0

######
favorite 0

######
comment 0

We define a special case of tree decompositions for planar graphs that respect a given embedding of the graph. We study the analogous width of the resulting decomposition we call the embedded-width of a plane graph. We show both upper bounds and lower bounds for the embedded-width of a graph in terms of its treewidth and describe a fixed parameter tractable algorithm to calculate the embedded-width of a plane graph. To do so, we give novel bounds on the size of matchings in planar graphs.

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1703.07532

3
3.0

Jun 27, 2018
06/18

by
D. S. Malyshev; O. O. Lobanova

texts

######
eye 3

######
favorite 0

######
comment 0

We show that determining the chromatic number of a $\{P_5,\bar{P_5}\}$-free graph or a $\{P_5,K_p-e\}$-free graph can be done in polynomial time

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1503.02550

3
3.0

Jun 27, 2018
06/18

by
Bastien Pasdeloup; Réda Alami; Vincent Gripon; Michael Rabbat

texts

######
eye 3

######
favorite 0

######
comment 0

The uncertainty principle states that a signal cannot be localized both in time and frequency. With the aim of extending this result to signals on graphs, Agaskar&Lu introduce notions of graph and spectral spreads. They show that a graph uncertainty principle holds for some families of unweighted graphs. This principle states that a signal cannot be simultaneously localized both in graph and spectral domains. In this paper, we aim to extend their work to weighted graphs. We show that a...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1503.03291

1
1.0

Jun 27, 2018
06/18

by
Tiziana Calamoneri; Blerina Sinaimeri; Mattia Gastaldello

texts

######
eye 1

######
favorite 0

######
comment 0

A graph G=(V,E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers `d' and `D' such that each leaf `u' of T is a node of V and the edge `(u,v) belongs to E' iff `d

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1504.06454

3
3.0

Jun 27, 2018
06/18

by
Friedrich Eisenbrand; Shay Moran; Rom Pinchasi; Martin Skutella

texts

######
eye 3

######
favorite 0

######
comment 0

Suppose you are given a graph $G=(V,E)$ with a weight assignment $w:V\rightarrow\mathbb{Z}$ and that your objective is to modify $w$ using legal steps such that all vertices will have the same weight, where in each legal step you are allowed to choose an edge and increment the weights of its end points by $1$. In this paper we study several variants of this problem for graphs and hypergraphs. On the combinatorial side we show connections with fundamental results from matching theory such as...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1504.06919

7
7.0

Jun 28, 2018
06/18

by
Gabriel Renault

texts

######
eye 7

######
favorite 0

######
comment 0

In normal version of combinatorial game theory, all games are invertible, whereas only the empty game is invertible in mis\`ere version. For this reason, several restricted universes were earlier considered for their study, in which more games are invertible. We here study combinatorial games in mis\`ere version, in particular universes where no player would like to pass their turn In these universes, we prove that having one extra condition makes all games become invertible. We then focus our...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1509.01576

1
1.0

Jun 28, 2018
06/18

by
Adrien Richard

texts

######
eye 1

######
favorite 0

######
comment 0

We are interested in the relationships between the number fixed points in a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ and its interaction graph, which is the arc-signed digraph $G$ on $\{1,\dots,n\}$ that describes the positive and negative influences between the components of the network. A fundamental theorem of Aracena says that if $G$ has no positive (resp. negative) cycle, then $f$ has at most (resp. at least) one fixed point; the sign of a cycle being the product of the signs of its arcs....

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1509.07702

2
2.0

Jun 27, 2018
06/18

by
Jayanta Kumar Das; Pabitra Pal Choudhury; Sudhakar Sahoo

texts

######
eye 2

######
favorite 0

######
comment 0

CVT and XOR are two binary operations together used to calculate the sum of two non-negative integers on using a recursive mechanism. In this present study the convergence behaviors of this recursive mechanism has been captured through a tree like structure named as CVT-XOR Tree. We have analyzed how to identify the parent nodes, leaf nodes and internal nodes in the CVT-XOR Tree. We also provide the parent information, depth information and the number of children of a node in different CVT-XOR...

Topics: Computing Research Repository, Discrete Mathematics

Source: http://arxiv.org/abs/1506.01544